/*
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/* $Id: queue.c 47 2007-09-21 08:39:29Z kf701.ye $ */

#include "queue.h"
#include "macro.h"


static _node_t *get_node_link_nth(queue_t *qu, uint32_t n);


/**
 * @brief create a queue
 * return queue
 */
queue_t *data_queue_new(void)
{
	queue_t *q = (queue_t*)malloc(sizeof(queue_t));
	q->head = q->tail = NULL;
	q->length = 0;
	return q;
}

/**
 * @brief delete a queue
 */
void data_queue_free(queue_t *qu)
{
	if( unlikely(NULL == qu) )
		return;

	void *data;
	while( (data = data_queue_pop_tail(qu)) )
	{
		free( data );
	}

	free( qu );
}

/**
 * @brief get length of queue
 */
uint32_t data_queue_length(queue_t *qu)
{
	if( unlikely(NULL == qu) )
		return 0;
	return qu->length;
}

/**
 * @brief push head of queue
 * @param qu	queue
 * @param data	node data
 */
void data_queue_push_head(queue_t *qu, void *data)
{
	if( unlikely(NULL == qu) )
		return;

	_node_t *node = (_node_t*)malloc(sizeof(_node_t));
	node->data = data;
	node->next = qu->head;
	node->prev = NULL;

	if( qu->head )
		qu->head->prev = node;
	qu->head = node;
	if( NULL == qu->tail )
		qu->tail = qu->head;
	qu->length++;
}

/**
 * @brief push tail of queue
 * @param qu	queue
 * @param data	node data
 */
void data_queue_push_tail(queue_t *qu, void *data)
{
	if( unlikely(NULL == qu) )
		return;

	_node_t *node = (_node_t*)malloc(sizeof(_node_t));
	node->data = data;
	node->next = NULL;
	node->prev = qu->tail;

	if( qu->tail )
		qu->tail->next = node;
	qu->tail = node;
	if( NULL == qu->head )
		qu->head = qu->tail;
	qu->length++;
}

/**
 * @brief push data at the nth of queue
 * @param qu	queue
 * @param data	node data
 */
void data_queue_push_nth(queue_t *qu, void *data, uint32_t n)
{
	if( unlikely(NULL == qu) )
		return;
	if( unlikely(n > qu->length) )
	{
		data_queue_push_tail(qu, data);
		return;
	}
	if( unlikely(n <= 1) )
	{
		data_queue_push_head(qu, data);
		return;
	}

	_node_t *node = (_node_t*)malloc(sizeof(_node_t));
	node->data = data;

	_node_t *p = get_node_link_nth(qu, n-1);

	node->next = p->next;
	node->prev = p;
	p->next = node;
	node->next->prev = node;

	qu->length++;
}

/**
 * @brief pop data at the head of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_pop_head(queue_t *qu)
{
	if( unlikely(NULL == qu) || unlikely(NULL == qu->head) )
		return NULL;

	_node_t *p = qu->head;
	qu->head = p->next;
	if( qu->head )
		qu->head->prev = NULL;
	else
		qu->tail = NULL;

	qu->length--;
	void *data = p->data;
	free( p );
	return data;
}

/**
 * @brief pop data at the tail of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_pop_tail(queue_t *qu)
{
	if( unlikely(NULL == qu) || unlikely(NULL == qu->tail) )
		return NULL;

	_node_t *p = qu->tail;
	qu->tail = p->prev;
	if( qu->tail )
		qu->tail->next = NULL;
	else
		qu->head = NULL;

	qu->length--;
	void *data = p->data;
	free( p );
	return data;
}

/**
 * @brief pop data at the nth of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_pop_nth(queue_t *qu, uint32_t n)
{
	if( unlikely(NULL == qu) )
		return NULL;
	if( n > qu->length )
		return data_queue_pop_tail(qu);
	if( n <= 1 )
		return data_queue_pop_head(qu);

	_node_t *p = get_node_link_nth(qu, n);

	_node_t *q = p->prev;
	q->next = p->next;
	p->next->prev = q;

	qu->length--;
	void *data = p->data;
	free( p );
	return data;
}

/**
 * @brief peek data at the head of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_peek_head(queue_t *qu)
{
	if( unlikely(NULL == qu) )
		return NULL;
	return qu->head ? qu->head->data : NULL;
}

/**
 * @brief peek data at the tail of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_peek_tail(queue_t *qu)
{
	if( unlikely(NULL == qu) )
		return NULL;
	return qu->tail ? qu->tail->data : NULL;
}

/**
 * @brief peek data at the nth of queue
 * @param qu	queue
 * @return	queue node data
 */
void *data_queue_peek_nth(queue_t *qu, uint32_t n)
{
	if( unlikely(NULL == qu) )
		return NULL;
	if( n > qu->length )
		return data_queue_peek_tail(qu);
	if( n <= 1 )
		return data_queue_peek_head(qu);

	_node_t *p = get_node_link_nth(qu, n);

	return p->data;
}

static _node_t *get_node_link_nth(queue_t *qu, uint32_t n)
{
	if( unlikely(NULL == qu) )
		return NULL;

	_node_t *p = NULL;
	if( n < qu->length / 2 )
	{
		p = qu->head;
		n = n - 1;
		while( n-- )
			p = p->next;
	}
	else
	{
		p = qu->tail;
		n = qu->length - n;
		while( n-- )
			p = p->prev;
	}
	return p;
}

